package com.sympsel.Dynamic_Programming_DP;


import org.junit.Test;

public class Demo {
    // 1
    public static int tribonacci1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    public static int tribonacci2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int[] dp = new int[4];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++) {
            dp[i % 4] = dp[(i - 1) % 4] + dp[(i - 2) % 4] + dp[(i - 3) % 4];
        }
        return dp[n % 4];
    }

    // 2
    public int waysToStep(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        int MOD = (int) 1e9 + 7;
        int a = 1, b = 2, c = 4, d = 0;
        for (int i = 4; i <= n; i++) {
            d = ((a + b) % MOD + c) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    @Test
    public void test1() {
        System.out.println(tribonacci1(25));
        System.out.println(tribonacci2(25));
    }

    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int a = cost[0];
        int b = cost[1];

        for (int i = 2; i < n; i++) {
            int c = Math.min(a, b) + cost[i];
            a = b;
            b = c;
        }

        return Math.min(a, b);
    }

    @Test
    public void test2() {
        int[] cost = {10, 15, 20};
        System.out.println(minCostClimbingStairs(cost));
    }

}
